/*
 * To change this template, choose Tools | Templates and open the template in
 * the editor.
 */
package AA;

/**
 *
 * @author asc
 */
public class P024
{
    public char[] cadenaA;
    public char[] cadenaB;
    int [][]distance;
    public int best(String[] args){
        String Sol="";
        cadenaA=args[0].toCharArray();
        cadenaB=args[1].toCharArray();
        distance = new int[cadenaA.length+1][cadenaB.length+1];
        computeLevenshteinDistance(cadenaA, cadenaB);
        return distance[cadenaA.length][cadenaB.length];
    }
    
    public static int minimum(int a, int b, int c) {
        if(a<=b && a<=c)
        {
            return a;
        } 
        if(b<=a && b<=c)
        {
            return b;
        }
        return c;
     }
 
    public int computeLevenshteinDistance(char [] str1, char [] str2) {
        for(int i=0;i<=str1.length;i++)
        {
                distance[i][0]=i;
        }
        for(int j=0;j<=str2.length;j++)
        {
                distance[0][j]=j;
        }
        for(int i=1;i<=str1.length;i++)
        {
            for(int j=1;j<=str2.length;j++)
            { 
                  distance[i][j]= minimum(distance[i-1][j]+1,
                                        distance[i][j-1]+1,
                                        distance[i-1][j-1]+
                                        ((str1[i-1]==str2[j-1])?0:1));
            }
        }
        return distance[str1.length][str2.length];
 
    }
}
